//1：三数之和 题目链接：https://leetcode.cn/problems/3sum/description/?envType=problem-list-v2&envId=two-pointers

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());//升序
        vector<vector<int>> vvt;
        //【a,b,c] : a + b + c == 0
        //基于三重循环 O(N^3 )
        //优化：左右双指针同时进行（第二重 和 第三重循环重叠）：固定a(第一重循环)，b增大，c减小
        //并且 每重循环的相邻枚举值不重复
        //达到时间复杂度O(N^2)
        int i = 0, size = nums.size();
        while (i < size - 2 && nums[i] <= 0)//固定a，第一重循环
        {
            int left = i + 1, right = size - 1;
            while (nums[right] >= 0 && left < right)//b和C的重叠进行
            {
                    int sum = nums[i] + nums[left] + nums[right];
                    if (0 == sum)//满足条件
                    {
                        vvt.push_back({nums[i], nums[left], nums[right]});
                         //调整right
                        int next_right = right - 1;
                        while (next_right > left && nums[next_right] == nums[right]) { --next_right; }
                        right = next_right;
                        //调整left
                        int next_left = left + 1;
                        while (next_left < right && nums[next_left] == nums[left]) { ++next_left; }
                        left = next_left;
                    }
                    else if (sum > 0)
                    {
                         //调整right
                        int next_right = right - 1;   
                        while (next_right > left && nums[next_right] == nums[right]) {--next_right;}
                        right = next_right;
                    }
                    else
                    {
                        //调整left
                        int next_left = left + 1;
                        while (next_left < right && nums[next_left] == nums[left]) {++next_left;}
                        left = next_left;
                    }
            }
            //调整i
            int next_i = i + 1;
            while (next_i < size && nums[next_i] == nums[i]) {++next_i;}
            i = next_i;
        }

        return vvt;
    }
};

//2：比较版本号  题目链接：https://leetcode.cn/problems/compare-version-numbers/description/?envType=problem-list-v2&envId=two-pointers&favoriteSlug=&difficulty=MEDIUM&status=ATTEMPTED%2CSOLVED
class Solution {
public:
    void String_to_figure(string& s, vector<int>& vt)
    {
        char* pch = strtok((char*)s.c_str(), ".");
        while (pch)
        {
            int length = strlen(pch);
            int index = length - 1, num = 0, i = 1;
            while (index >= 0)
            {
                num += (pch[index] - '0') * i;
                if (i != 1000000000) {i *= 10;}
                --index;
            }
            vt.push_back(num);
            pch = strtok(nullptr, ".");
        }
    }
    int compareVersion(string version1, string version2) {
        vector<int> v1, v2;
        string tmp1 = version1, tmp2 = version2;
        String_to_figure(tmp1, v1);
        String_to_figure(tmp2, v2);
        int size1 = v1.size(), size2 = v2.size(), i = 0, j = 0;
        while (i < size1 && j < size2)
        {
            if (v1[i] < v2[j]) { return -1; }
            else if (v1[i] > v2[j]) { return 1; }
            else {
                ++i;
                ++j;
            }
        }
        while (i < size1) 
        {
            if (v1[i] > 0) { return 1; }
            ++i;
        }
        while (j < size2)
        {
            if (v2[j] > 0) { return -1; }
            ++j;
        }
        return 0;
    }
};
